//============================================================================
// Name        : kmp.cpp
// Author      : weiwei
// Version     : V1.0
// Date        : 2014-06-23
// Copyright   : Your copyright notice
// Description : KMP算法，参考资料：算法导论第二版
//============================================================================

#include <iostream>
#include <string>
using namespace std;
#define max 20

//t:要搜索的字符串，next是t每次匹配时的偏移量
void getnext(const string &t,int* next);

//s:母串  t：待匹配的字串
void KMPindex(const string &s, const string &t);

int main()
{
    string s;
    string t;
    cout<<"partent string"<<endl;
    cin>>s;
    cout<<"son string"<<endl;
    cin>>t;
    KMPindex(s,t);
    return 0;
}

void getnext(const string &t,int* next)
{
    size_t t_len=t.size();
    int LOLP=0; // Lenth of longest prefix

    next[1]=0;
    for( int NOCM=2; NOCM<t_len+1; NOCM++ )// NOCM represent the number of characters matched
    {
        while(LOLP>0 && t[NOCM]!=t[LOLP+1]) LOLP=next[LOLP];
        if(t[NOCM]==t[LOLP+1]) LOLP++;
        next[NOCM]=LOLP;
    }
}

void KMPindex(const string &s, const string &t)
{
    bool flag=false;
    size_t sLen=s.size();
    size_t tLen=t.size();
    int next[max]= {0};
    getnext(t,next);
    int matched=0; // number of characters matched
    for(int i=0; i<sLen; i++)
    {
        while(matched>0 && t[matched]!=s[i]) matched = next[matched]; //next character doesn't matched
        if(t[matched]==s[i]) matched++;  //next character matched
        if(matched==tLen)
        {
            flag=true;
            cout<<"matched at: "<<i-tLen +1<<endl;
        }
    }
    if(!flag)
    {
        cout<<"sorry, the substring mismatched!!"<<endl;
    }
}
